//https://www.bilibili.com/video/BV1d54y1f7B3?spm_id_from=333.788.videopod.episodes&vd_source=d6fe65f095f01f05591e89d810720ccc&p=20
// 2024-10-21

public class P024_柠檬水找零_贪心算法 {

    public static void main(String[] args) {
        System.out.println(fun(new int[] {5,5,5,20}));
    }

    private static boolean fun(int[] customs) {
        int money_5 = 0,money_10 = 0;
        for (int custom : customs) {
            if (custom == 5) {
                money_5++;
            } else if (custom == 10) {
                if (money_5 == 0) return false;
                money_5--;
                money_10++;
            } else {
                //给的20，贪心算法，局部最优（5块万能，尽量多保留5块）
                if (money_10 > 0 && money_5 > 0) {
                    money_10--;
                    money_5--;
                } else if (money_5 >= 3) {
                    money_5 -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}
